Colorimetry has long been recognized as a complex science. Essentially, as defined in 1931 by the Commission Internationale L'Eclairage (CIE), three primary colors (X, Y, Z) can be combined to define all light sensations we experience with our eyes; that is, the color matching properties of an ideal trichromatic observer defined by specifying three independent functions of wavelength that are identified with the ideal observer's color matching functions form an international standard for specifying color. In general, it has been found possible and convenient to represent color stimuli vectors by a three-dimensional spatial construct, called a tristimulus space or a color space. The fundamentals of such three-dimensional constructs are discussed in the literature, such as Principles of Color Technology, by Billmeyer and Saltzman, published by John Wiley & Sons, Inc., NY, copyright 1981 (2d. ed.) and Color Science: Concepts and Methods, Quantitative Data and Formulae, by Wyszecki and Stiles, published by John Wiley & Sons, Inc., copyright 1982 (2d ed.), incorporated herein by reference in pertinent parts, particularly pages 119-130.
A variety of trichromatic model systems--such as the red, green, blue (RGB) model; the cyan, magenta, yellow (and black) (CMY(K)) model; the hue, saturation, value (HSV) model; the hue, lightness, saturation (HLS) model; the luminance, red-yellow scale, green-blue scale (L*a*b*) model; the YIQ model used in commercial color television broadcasting; and others--provide alternatives for the system designer. Such works as Fundamentals of Interactive Computer Graphics, by Foley and Van Dam, Addison-Wesley Publishing Company, incorporated herein by reference in pertinent parts, particularly pages 606-621, describe a variety of tri-variable color models.
Color input and output devices--such a scanners, cathode ray tube (CRT) video monitors, and printers--present color images in a device-dependent fashion. For example, CRT guns are driven by RGB values (voltage levels or other input signal functions, referred to hereinafter as data triplets) that are stored in a frame buffer. Those RGB values index over the color space of each particular model video monitor; in other words, the color produced by a CRT on a pixel of its screen for a given RGB triplet of values is unique to that device. Because of device design dependency, the same RGB triplet may produce a very different color or hue when displayed on a different model CRT and still a different color in a hard copy made with a color printer.
Color transformation (also referred to in the art as color correction and cross-rendering) between model systems in digital data processing presents many problems to the original equipment manufacturer. The transformation of data from one device to another device is difficult because the color matching relationship between those systems are generally non-linear. Therefore, a crucial problem is the maintaining of color integrity between an original image from an input device (such as a color scanner, CRT monitor, digital camera, computer software/firmware generation, and the like) and a translated copy at an output device (such as a CRT monitor, color laser printer, color ink-jet printer, and the like).
As discussed in the reference materials cited above, colors can be constructed as renderings of the additive primary colors, red, green, and blue (RGB), or of the subtractive primary colors, cyan, magenta, yellow and black (CMYK). A transformation may require going from an RGB color space, for example, a computer video monitor, to a CMYK color space, for example, a laser printer hard copy. A transformation from one color space to another requires complex, non-linear computations in multiple dimensions. Since such is not describable mathematically, the use of very large look-up tables, e.g. 50 megabytes, containing data to approximate a transformation is generally required to go from an RGB system to a CMYK system to correlate a wide spectrum of color hues. [Note: To maintain black color purity in CMYK printing, a separate black ink or toner is usually provided rather than printing all three cyan, magenta and yellow colors as a composite black; the use of such a separate black rendition mechanism is assumed for the purpose of disclosing the present invention.] A lookup table of input versus output data can be generated for any set of devices. There are a variety of methods for building a device-dependent look-up table for a particular device. U.S. Pat. No. 3,893,166 (Pugsley) provides an example. However, semiconductor memory is relatively expensive and other data storage technologies for maintaining such tables--disks, tape, and the like--are too slow.
Therefore, there is a need for a process that transforms the color values from one particular device color space into the color space of another device in a fast, economical manner.
Bytes of data correlated in three dimensions can be represented as a cubic lattice construct with each corner of a cube representing a data point. The total look-up table is made of many such cubes as shown in FIG. 1 for an RGB, or other model, color space construct. However, to store a typical printer color transformation data point value for every monitor RGB value in a look-up table would require about fifty megabyte of memory which is cost prohibitive in the state-of-the-art. Thus, it is economic to store only a limited number of data points and to use interpolation methods to derive intermediate data points within the lattice.
Transforming CRT video monitor RGB triplets into printer RGB (or CMY, or CMYK) values can be accomplished by utilizing color measurement tools and device-color spaces. Device-independent color provides accurate color matching based on an absolute color standard, such as the CIE. A device-independent color space provides a way for describing the appearance of a color without referring to the mechanism that produced the color. For example:
first, a function is constructed that transforms RGB data points from the color space of a monitor (that is, the table of input-output correlations) into a device-independent color space, e.g., the CIE L*a*b* color space; PA1 second, a function is constructed that transforms color data points from the device-independent color space, the CIE L*a*b* color space, into the color space of a particular printer; and PA1 using these two functions, the monitor RGB data values can be transformed to L*a*b* data triplets and the L*a*b* data triplets transformed into the printer data triplets, thus providing printer output that matches the original output as viewed on the CRT monitor.
However, in addition to the data storage and access problems referred to above, the mapping of the monitor RGB values into printer RGB values is time intensive to perform on each and every colored pixel in an image before completely printing that image. Therefore, it is economic to pre-compute and store the printer output RGB values for a subset of monitor input RGB values and then to use a fast interpolation algorithm to approximate the transform function for intermediate RGB values, namely those that have not been pre-computed and stored.
In making the transform from one tristimulus system to another, trilinear or quadrilinear interpolation methods as would be known to a person skilled in the art have been used. One purported device for an algorithmic interpolation solution using the L*a*b* model is described briefly in Electronic Engineering Times, Nov. 9, 1992, page 35, High-speed processor transforms colors, by Junko Yoshida. However, Yoshida's "new algorithm" itself is not disclosed. A commonality of such interpolator solutions is that they must access data for the three or more variables simultaneously, namely, in parallel, in order to obtain the fastest speed, requiring either redundant data tables or complex storage access mechanisms. Moreover, such interpolation methods require multiplication and division mathematical operations which require complex and expensive hardware.
There is a need for a fast and economical method for storing limited points of an output data table and interpolating the stored data to obtain a proper transform between multi-variable data processing systems.